package Lintcode;

import calltimer.CallTimer;
import calltimer.annotations.MethodAlias;


import java.util.Scanner;

/**
 * Question: https://www.lintcode.com/zh-cn/problem/trailing-zeros/
 * Solution: 基本思路，相乘后能够产生0的，只有是10的倍数，而10可以分解为5*2，所以可以将
 * 阶乘中的每个数质因子分解后，统计其中（5,2）的对数。而在分解因子后，发现质因子中，2的数量
 * 肯定比5多，所以问题的最终转化为求质因子中5的个数。
 * Time: 2018/4/12
 * Coder: Ksxy
**/
public class TrailingZeros {

    static Scanner scanner = null;

    static {
        scanner = new Scanner(System.in);
    }

    public static void main(String[] args) {
        int n = scanner.nextInt();
        CallTimer.call(TrailingZeros.class, "trailingZeros1", n);
        CallTimer.call(TrailingZeros.class, "trailingZeros2", n);
    }


    /**
     * Desc: 时间复杂度O(N)
     * 遍历小于等于n中，为5的倍数的数，求每个数分解后包含5的个数
     **/
    @MethodAlias(alias = "trailingZeros1")
    public static int trailingZeros1(int n){
        int result = 0;
        for (int i = 5; i <= n; i+=5){
            int temp = hasFive(i);
            result += temp;
        }
        return result;
    }

    private static int count = 0;
    private static int hasFive(int n){
        count = 0;
        calculate(n);
        return count;
    }

    //递归求因子中5的个数
    private static void calculate(int n) {
        if(n%5 == 0){
            count++;
            calculate(n/5);
        }
    }


    /**
     * Desc: 时间复杂度O(logN)
     * ⒈（1, 2, 3, 4, 5, ..., n）中，先考虑为5的倍数，有（5, 10, 15, 20, 25, ...）一共n/5个数。
     * 集合中像5,10,15,20,30这数的因子中都只有一个5，而25有两个5，那我要判断这些数中，哪些数的
     * 因子有多个5，只要将这些数都除以5后，看他是否是5的倍数。
     * ⒉ 那么，提取5，集合可表示为5*（1,2,3,4,5,...）,然考虑5的倍数，有（5,10,15,...）一共n/25个数。
     * ⒊ 5*5*（1,2,3,...）,(5,10,15,...)一共有n/125个数。
     * 只要重复以上过程，直到集合中的元素为空，将每一轮集合中元素的个数累积，最后就是所有数的因子中，5
     * 的个数。
     **/
    @MethodAlias(alias = "trailingZeros2")
    public static int trailingZeros2(int n){
        int count = 0;
        int temp = n/5;
        while (temp != 0){
            count += temp;
            temp = temp/5;
        }
        return count;
    }

}
